package leetcode;

/**
 * @author Liangyaoyun
 */
public class leetCode240 {
      public boolean searchMatrix(int[][] matrix, int target) {
        int i=0;
        int j=matrix[0].length-1;
        return findTarget(matrix,target,false,i,j);
      }
      public boolean findTarget(int[][] matrix,int target,boolean flag,int i,int j){
          if (i>matrix.length||j<0){
              return false;
          }
          if (target==matrix[i][j]){
              return true;
          }
          if (i< matrix.length&&j>=0){
              if (target>matrix[i][j]){
                  flag=findTarget(matrix,target,flag,i+1,j);
              }else {
                  flag=findTarget(matrix,target,flag,i,j-1);
              }
          }
          else {
              return false;
          }
          return flag;
      }

  public static void main(String[] args) {
      int[][] matrix=new int[][]{{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
      int target=5;
      leetCode240 leetcode240=new leetCode240();
      System.out.println(leetcode240.searchMatrix(matrix, target));
  }
}
